﻿//using Nemerle.Collections;
using Nemerle.Text;
using Nemerle.Utility;
using Nemerle.Assertions;

using System;
using System.Collections.Generic;
using System.Linq;

using SC = System.Collections;

namespace Nemerle.Data
{
  public module Arrays
  {
    //-------------
    // Conversions
    //-------------
    
    
    public ToSeq[T](
      [NotNull] this arr : array[T]
    ) : Seq[T]
    {
       foreach(elem in arr) yield elem
    }
    
    public ToNList'[T](
      [NotNull] this arr : array[T]
    ) : list[T]
    {
      $[x | x in arr]
    }
    
    public ToNList[T](
      [NotNull] this arr : array[T]
    ) : list[T]
    {
      mutable res = [];
      foreach(i in [arr.Length-1, arr.Length-2 .. 0])
        res ::= arr[i];
      res      
    }
    
    public TakeToNList[T](
      [NotNull] this arr : array[T],
      c : int
    ) : list[T]
    {
      mutable res = [];
      foreach(i in [c-1, c-2 .. 0])
        res ::= arr[i];
      res      
    }
    
    public TakeToNList'[T](
      [NotNull] this arr : array[T],
      c : int
    ) : list[T]
    {
      $[ arr[i] | i in [c-1, c-2 .. 0]]
    }
    
    public ToNList''[T](
      [NotNull] this arr : array[T]
    ) : list[T]
    {
      def loop(s, i) {
        if (i < 0) s else loop(arr[i] :: s, i - 1)
      }
      loop([], arr.Length - 1)
    }
    
    public ToNList'''[T](
      [NotNull] this arr : array[T]
    ) : list[T]
    {
      mutable res = [];
      for(mutable i = arr.Length-1; i >= 0; i--)
        res ::= arr[i];
      res
    }
    
    //-------------
    // Iterations
    //-------------
    
    /// <summary>
    /// Performs the specified action on each element of the array.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="arr">The array.</param>
    /// <param name="action">The action.</param>
    public Iter[T](
      [NotNull] this arr : array[T],
      [NotNull]   action : T -> void
    ) : void
    {
      foreach(elem in arr) 
        action(elem) 
    }
    
    /// <summary>
    /// Performs the specified action on each element of the array 
    /// by incorporating the element's index.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="sequence">The array.</param>
    /// <param name="action">The action.</param>
    public IterI[T](
      [NotNull] this arr : array[T],
      [NotNull]   action : int * T -> void
    ) : void
    {
      foreach(elem in arr with i) 
        action(i, elem) 
    }
    
    //------------------
    // Basic functions
    //------------------
    
    
    public Append[T](
      [NotNull] this arr : array[T],
                    item : T
    ) : array[T]
    {
      def res = array(arr.Length + 1);
      Array.Copy(arr, 0, res, 0, arr.Length);
      res[arr.Length] = item;
      res
    }
    
    
    public Prepend[T](
      [NotNull] this arr : array[T],
                    item : T
    ) : array[T]
    {
      def res = array(arr.Length + 1);
      Array.Copy(arr, 0, res, 1, arr.Length);
      res[0] = item;
      res
    }
    
    /// <summary>
    /// Returns an empty array that has the specified type argument.
    /// </summary>
    /// <typeparam name="T">The type to assign to the type parameter of the returned array.</typeparam>
    public Empty[T]() : array[T]
    {
      array(0)
    }
    
    /// <summary>
    /// Returns an array that contains one item only.
    /// </summary>
    /// <param name="elem"></param>
    /// <typeparam name="T"></typeparam>
    public Single[T](
      elem : T
    ) : array[T]
    {
      array[elem]
    }
    
    //public @+[T](
    //  [NotNull] left : array[T],
    //  [NotNull] right : array[T]
    //) : array[T]
    //{
    //  def result = array(left.Length + right.Length)
    //}
    
    
    public IsEmpty[T](
      this arr : array[T]
    ) : bool
    {
      arr.Length == 0 
    }
   
    
    public MaxIndex[T](
      this arr : array[T]
    ) : int
    {
      arr.Length - 1
    }
    
    #warning not tested    
    public MaxIndex[T](
      this collection : IList[T]
    ) : int
    {
      collection.Count - 1
    }    
    
    public IsNullOrEmpty[T](
      this arr : array[T]
    ) : bool
    {
      arr : object == null || arr.Length == 0 
    }
    
    //public CheckLength[T](
    //  [NotNull] this source : Seq[T]
    //) : bool
    //{
      
    //}
    
    /// <summary>
    /// Extract the first element of an array, which must be non-empty.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="source"></param>
    /// <returns></returns>
    public Head[T](
      [NotNull] this source : array[T]
    ) : T
    {
      source[0]
    }
    
    /// <summary>
    /// Extract the first element of an array or None.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="source"></param>
    /// <returns></returns>
    public HeadOrNone[T](
      [NotNull] this source : array[T]
    ) : option[T]
    {
      if(source.Length > 0) Some(source[0]) else None()
    }
    
    /// <summary>Returns all elements of the array except the first as a new array.</summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="arr">The array.</param>
    /// <returns></returns>
    public Tail[T](
      [NotNull] this arr : array[T]
    ) : array[T]
    {
      arr.DropExactly(1)
    }
    
    /// <summary>
    /// Returns all elements of the array except the first as a new array or None.
    /// </summary>
    #warning not tested
    public TailOrNone[T](
      [NotNull] this arr : array[T]
    ) : option[array[T]]
    {
      if(arr.Length > 0)
        Some(arr.DropExactly(1))
      else
        None()
    }
    
    /// <summary>Returns the last element of an array.</summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="arr">The array.</param>
    /// <returns></returns>
    public LastElem[T](
      [NotNull] this arr : array[T]
    ) : T
    {
      arr[arr.Length-1]
    }
    
    /// <summary>
    /// Returns the last element of an array or None.
    /// </summary>
    #warning not tested
    public LastElemOrNone[T](
      [NotNull] this arr : array[T]
    ) : option[T]
    {
      if(arr.Length > 0)
        Some(arr[arr.Length-1])
      else
        None()
    }
    
    /// <summary>
    /// Return all the elements of an array except the last one as a new array. 
    /// The array must be non-empty.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="sequence">The sequence.</param>
    /// <returns></returns>
    public Init[T](
      [NotNull] this arr : array[T]
    ) : array[T]
    {
      arr.DropRightExactly(1)
    }
    
    /// <summary>
    /// Return all the elements of an array except the last one as a new array or None. 
    /// The array must be non-empty.
    /// </summary>
    #warning not tested
    public InitOrNone[T](
      [NotNull] this arr : array[T]
    ) : option[array[T]]
    {
      if(arr.Length > 0)
        Some(arr.DropRight(1))
      else
        None()
    }
    
    /// <summary>
    /// Copies elements in an array.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="arr">The array.</param>
    /// <returns></returns>
    public Copy[T](
      [NotNull] this arr : array[T]
    ) : array[T]
    {
      def result = array(arr.Length);
      Array.Copy(arr, result, arr.Length);
      result
    }
    
    /// <summary>
    /// Inverts the order of the elements in an array.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="arr">The array.</param>
    /// <returns></returns>
    public Rev[T](
      [NotNull] this arr : array[T]
    ) : array[T]
    {
      def result = arr.Copy();
      Array.Reverse(result);
      result
    }
    
    //--------------------------
    // Sequence transformations
    //--------------------------
    
    /// <summary>
    /// Creates a new array whose elements are the results of applying 
    /// the given function f to each of the elements of the array source. 
    /// </summary>
    /// <typeparam name="From"></typeparam>
    /// <typeparam name="To">The type of the result.</typeparam>
    /// <param name="source">The sequence.</param>
    /// <param name="f">The function.</param>
    /// <returns></returns>
    public Map[From, To](
      [NotNull] this source : array[From],
      [NotNull] f           : From -> To
    ) : array[To]
    {
      def result = array(source.Length);
      foreach(x in source with i)
        result[i] = f(x);
      result
    }
    
    /// <summary>
    /// Creates a new array whose elements are the results of applying 
    /// the given function f to each of the elements of the array source.
    /// The integer passed to the function indicates the index of element.
    /// </summary>
    /// <typeparam name="From"></typeparam>
    /// <typeparam name="To">The type of the result.</typeparam>
    /// <param name="source">The sequence.</param>
    /// <param name="f">The function.</param>
    /// <returns></returns>
    public MapI[From, To](
      [NotNull] this source : array[From],
      [NotNull] f           : int * From -> To
    ) : array[To]
    {
      def result = array(source.Length);
      foreach(x in source with i)
        result[i] = f(i, x);
      result
    }
    
    /// <summary>
    /// Intersperses an element between all members of the specified array.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="arr">The array.</param>
    /// <param name="separator">The separator.</param>
    /// <returns></returns>
    /// <example>
    /// <c>"abcde".Intersperse(',') == "a,b,c,d,e"</c>
    /// </example>
    public Intersperse[T](
      [NotNull] this arr : array[T], 
               separator : T
    ) : array[T]
    {
      if (arr.Length > 0)
      {
        def result = array(arr.Length * 2 - 1);
        result[0] = arr[0];
        foreach(i in [1 .. arr.Length - 1])
        {
          def j = i * 2;
          result[j - 1] = separator;
          result[j] = arr[i];
        }
        result
      }
      else
        array(0)
    }
    
    
    public IntersperseWith[T](
      [NotNull] this arr : array[T], 
                     f   : T * T -> T
    ) : array[T]
    {
      if (arr.Length > 0)
      {
        def result = array(arr.Length * 2 - 1);
        result[0] = arr[0];
        foreach(i in [1 .. arr.Length - 1])
        {
          def j = i * 2;
          result[j - 1] = f(arr[i - 1], arr[i]);
          result[j] = arr[i];
        }
        result
      }
      else
        array(0)
    }
    
    /// <summary>
    /// Equivalent to <c>arr.Intersperse(separator).Concatenate()</c>.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="arr">The array.</param>
    /// <param name="separator">The separator.</param>
    /// <returns></returns>
    /// <remarks>
    /// This is a more general form of <see cref="string.Join(string,string[])"/>
    /// </remarks>
    public Intercalate[T](
      [NotNull] this arr : array[array[T]], 
               separator : array[T]
    ) : array[T]
    {
      arr.Intersperse(separator).Concatenate()
    }
    
    
    public Transpose[T](
      [NotNull] this arrs : array[array[T]]
    ) : array[array[T]]
    {
      if(arrs.Length > 0)
      {
        def rc = arrs[0].Length;
        def lc = arrs.Length;
        def res = array(rc);
        foreach(_ in res with i) res[i] = array(lc);
        foreach(line in arrs with i)
          foreach(x in line with j)
           res[j][i] = x;
        res
      }
      else
        array(0)
    }
    
    
    public MapOption[From, To](
      [NotNull] this source : array[From],
      [NotNull] f           : From -> option[To]
    ) : array[To]
    {
      def result = List(source.Length);
      foreach(x in source)
      {
        def res = f(x);
        when(res.IsSome) result.Add(res.Value);
      }
      result.ToArray()
    }
    
    
    public CatOptions[T](
      [NotNull] this source : array[option[T]]
    ) : array[T]
    {
      def result = List(source.Length);
      foreach(Some(x) in source)
        result.Add(x);
      result.ToArray()
    }
    
    /// <summary>
    /// Creates a new array whose elements are the results of applying 
    /// the given function f to each element in the input array and its predecessor, 
    /// with the exception of the first element which is only used as the predecessor 
    /// of the second element.
    /// </summary>
    /// <typeparam name="From"></typeparam>
    /// <typeparam name="To">The type of the result.</typeparam>
    /// <param name="source">The sequence.</param>
    /// <param name="f">The function.</param>
    public PairwiseWith[From, To](
      [NotNull] this source : array[From],
      [NotNull] f           : From * From -> To
    ) : array[To]
    {
      if (source.Length > 1)
      {
        def result = array(source.Length - 1);
        foreach(i in [0 .. source.Length - 2])
          result[i] = f(source[i], source[i + 1]);
        result
      }
      else
        array(0)
    }
    
    #warning not tested
    public Pairwise[T](
      [NotNull] this source : array[T],
    ) : array[T * T]
    {
      if (source.Length > 1)
      {
        def result = array(source.Length - 1);
        foreach(i in [0 .. source.Length - 2])
          result[i] = (source[i], source[i + 1]);
        result
      }
      else
        array(0)
    }
    
    
    public ReducePairs[From, To](
      [NotNull] this source : array[From],
      [NotNull] f           : From * From -> To
    ) : array[To]
    {
      if(source.Length > 1)
      {
        def result = array(source.Length/2);
        foreach(i in [0 .. source.Length/2 - 1])
        {
          def j = i*2;
          result[i] = f(source[j], source[j + 1]);
        }
        result
      }
      else
        array(0)
    }
    
    //-----------------------------
    // Reducing sequences (folds)
    //-----------------------------
    
    /// <summary>
    /// Reduces the array from left to right using the specified 
    /// binary function f starting with the specified accumulator value.
    /// </summary>
    /// <typeparam name="T">The type of the elements in the array.</typeparam>
    /// <typeparam name="TAccumulator">The type of the accumulator.</typeparam>
    /// <param name="arr">The sequence to fold.</param>
    /// <param name="f">The binary function.</param>
    /// <param name="acc">The initial value of the accumulator.</param>
    /// <returns>The final accumulator value.</returns>
    public Fold[TAccumulator, T](
      [NotNull] this arr : array[T],
      mutable   acc      : TAccumulator,
      [NotNull] f        : TAccumulator * T -> TAccumulator
    ) : TAccumulator
    {
      foreach (value in arr)
        acc = f(acc, value);
      acc
    }
    
    
    public FoldOption[TAcc, T](
      [NotNull] this arr : array[T],
      mutable   acc      : TAcc,
      [NotNull] f        : TAcc * T -> option[TAcc]
    ) : TAcc
    {
      exit : {
        foreach(elem in arr)
        {
          def res = f(acc, elem);
          when (res.IsNone) exit(acc);
          acc = res.Value;
        }
        acc
      }
    }
    
    
    public FoldWhile[TAcc, T](
      [NotNull] this arr : array[T],
      mutable   acc      : TAcc,
      [NotNull] f        : TAcc * T -> TAcc,
      [NotNull] pred     : TAcc -> bool
    ) : TAcc
    {
      exit : {
        foreach(elem in arr)
        {
          def res = f(acc, elem);
          unless (pred(res)) exit(acc);
          acc = res;
        }
        acc
      }
    }
    
    /// <summary>
    /// Reduces the array from right to left using the specified binary function f
    /// starting with the specified accumulator value.
    /// </summary>
    /// <typeparam name="T">The type of the elements in the array.</typeparam>
    /// <typeparam name="TAccumulator">The type of the accumulator.</typeparam>
    /// <param name="arr">The sequence to fold.</param>
    /// <param name="f">The binary function used to calculate.</param>
    /// <param name="acc">The initial value of the accumulator.</param>
    /// <returns>The final accumulator value.</returns>
    public FoldRight[TAccumulator, T](
      [NotNull] this arr : array[T],
      mutable   acc      : TAccumulator,
      [NotNull] f        : T * TAccumulator -> TAccumulator
    ) : TAccumulator
    {
      foreach (i in [arr.Length-1, arr.Length-2 .. 0])
        acc = f(arr[i], acc);
      acc
    }
    
    /// <summary>
    /// Reduces the array from left to right using the specified binary function and
    /// starting with the first element of the sequence.
    /// </summary>
    /// <typeparam name="T">The type of the elements in the sequence.</typeparam>
    /// <param name="arr">The array to fold.</param>
    /// <param name="f">The binary function.</param>
    /// <returns>The final accumulator value.</returns>
    public Reduce[T](
      [NotNull] this arr : array[T],
      [NotNull] f : T * T -> T
    ) : T
    requires arr.Length > 0 
    {
      mutable acc = arr[0];
      foreach (i in [1..arr.Length-1])
        acc = f(acc, arr[i]);
      acc
    }
    
    /// <summary>
    /// Reduces the array from left to right using the specified binary function and
    /// starting with the first element of the sequence.
    /// </summary>
    /// <param name="arr">The array to fold.</param>
    /// <param name="f">The binary function.</param>
    /// <returns>The final accumulator value or none.</returns>
    public ReduceOrNone[T](
      [NotNull] this arr : array[T],
      [NotNull] f : T * T -> T
    ) : option[T]
    {
      if(arr.Length > 0)
        Some(arr.Reduce(f))
      else
        None()
    }
    
    /// <summary>
    /// Reduces the array from right to left using the specified binary function and
    /// starting with the last element of the sequence.
    /// </summary>
    /// <typeparam name="T">The type of the elements in the sequence.</typeparam>
    /// <param name="arr">The sequence to fold.</param>
    /// <param name="f">The binary function used to calculate .</param>
    /// <returns>The final accumulator value.</returns>
    public ReduceRight[T](
      [NotNull] this arr : array[T],
      [NotNull] f        : T * T -> T
    ) : T
    requires arr.Length > 0 
    {
      match (arr.Length)
      {
        | 1 => arr[0]
        | 2 => f(arr[0], arr[1])
        | _ => {
          mutable acc = arr.LastElem();
          foreach (i in [arr.Length-2, arr.Length-3 .. 0])
            acc = f(arr[i], acc);
          acc
        }
      }
    }
    
    /// <summary>
    /// Reduces the array from left to right using the specified 
    /// binary function f starting with the specified accumulator value.
    /// The integer passed to the function indicates the index of element.
    /// </summary>
    /// <typeparam name="T">The type of the elements in the array.</typeparam>
    /// <typeparam name="TAccumulator">The type of the accumulator.</typeparam>
    /// <param name="arr">The sequence to fold.</param>
    /// <param name="f">The binary function.</param>
    /// <param name="acc">The initial value of the accumulator.</param>
    /// <returns>The final accumulator value.</returns>
    public FoldI[TAccumulator, T](
      [NotNull] this arr : array[T],
      mutable   acc      : TAccumulator,
      [NotNull] f        : int * TAccumulator * T -> TAccumulator
    ) : TAccumulator
    {
      foreach (value in arr with i)
        acc = f(i, acc, value);
      acc
    }
    
    /// <summary>
    /// Reduces the array from right to left using the specified binary function f
    /// starting with the specified accumulator value.
    /// The integer passed to the function indicates the index of element.
    /// </summary>
    /// <typeparam name="T">The type of the elements in the array.</typeparam>
    /// <typeparam name="TAccumulator">The type of the accumulator.</typeparam>
    /// <param name="arr">The sequence to fold.</param>
    /// <param name="f">The binary function used to calculate.</param>
    /// <param name="acc">The initial value of the accumulator.</param>
    /// <returns>The final accumulator value.</returns>
    public FoldRightI[TAccumulator, T](
      [NotNull] this arr : array[T],
      mutable   acc      : TAccumulator,
      [NotNull] f        : int * T * TAccumulator -> TAccumulator
    ) : TAccumulator
    {
      foreach (i in [arr.Length-1, arr.Length-2 .. 0])
        acc = f(i, arr[i], acc);
      acc
    }
    
    //TODO Short Circuit Folds
    
    //----------------
    // Special folds
    //----------------
    
    //Flatten?
    
    public Concatenate[T](
      [NotNull] this arrs : array[array[T]],
    ) : array[T]
    {
      mutable sLength = 0;
      foreach(arr in arrs)
        sLength += arr.Length;
      def result = array(sLength);
      mutable cur = 0;
      foreach(arr in arrs)
      {
        Array.Copy(arr, 0, result, cur, arr.Length);
        cur += arr.Length;
      }
      result
    }
    
    
    public Concatenate[T](
      [NotNull] this arr1 : array[T],
      [NotNull]      arr2 : array[T]
    ) : array[T]
    {
      def result = array(arr1.Length + arr2.Length);
      Array.Copy(arr1, 0, result, 0, arr1.Length);
      Array.Copy(arr2, 0, result, arr1.Length, arr2.Length);
      result
    }
    
    /// <summary>
    /// Map a function over an array and concatenate the results.
    /// </summary>
    /// <typeparam name="From"></typeparam>
    /// <typeparam name="To">The type of the result.</typeparam>
    /// <param name="source">The array.</param>
    /// <param name="f">The function.</param>
    /// <returns></returns>
    public ConcatMap[From, To](
      [NotNull] this arr : array[From],
      [NotNull] f        : From -> array[To]
    ) : array[To]
    {
      def buffer = List();
      foreach(elem in arr)
        buffer.AddRange(f(elem));
      buffer.ToArray()
    }
    
    //
    //#warning not tested
    //public ConcatMap[From, To](
    //  [NotNull] this arr : List[From],
    //  [NotNull] f        : From -> array[To]
    //) : List[To]
    //{
    //  def buffer = List();
    //  foreach(elem in arr)
    //    buffer.AddRange(f(elem));
    //  buffer
    //}
    
    
    public Exist[T](
      [NotNull] this arr : array[T],
      [NotNull] f        : T -> bool
    ) : bool
    {
      exit : {
       foreach(elem in arr)
         when(f(elem)) exit(true);
       false
      }
    }
    
    
    public ForAll[T](
      [NotNull] this arr : array[T],
      [NotNull] f        : T -> bool
    ) : bool
    {
      exit : {
       foreach(elem in arr)
         unless(f(elem)) exit(false);
       true
      }
    }
    
    /// <summary>
    /// Returns the disjunction of an array of <see cref="bool"/>s.
    /// </summary>
    /// <param name="bools">The array of booleans.</param>
    /// <returns>The disjunction.</returns>
    public Or(
      [NotNull] this arr : array[bool],
    ) : bool
    {
      exit : {
       foreach(elem in arr)
         when(elem) exit(true);
       false
      }
    }
    
    /// <summary>
    /// Returns the conjunction of an array of <see cref="bool"/>s.
    /// </summary>
    /// <param name="bools">The array of booleans.</param>
    /// <returns>The conjunction.</returns>
    public And(
      [NotNull] this arr : array[bool],
    ) : bool
    {
      exit : {
       foreach(elem in arr)
         unless(elem) exit(false);
       true
      }
    }
    
    
    public Maximum[T](
      [NotNull] this arr : array[T]
    ) : T
    where T : IComparable[T]
    requires arr.Length > 0
    {
      mutable res = arr[0];
      foreach(elem in arr)
        when(elem.CompareTo(res) > 0) res = elem;
      res
    }
    
    
    public MaximumBy[T, K](
      [NotNull] this arr : array[T],
      [NotNull] selector : T -> K
    ) : T
    where K : IComparable[K]
    requires arr.Length > 0
    {
      mutable res = arr[0];
      mutable key = selector(res);
      foreach(elem in arr)
        when(selector(elem).CompareTo(key) > 0)
        {
          res = elem;
          key = selector(res);
        };
      res
    }
    
    
    public MaximumsBy[T, K](
      [NotNull] this arr : array[T],
      [NotNull] selector : T -> K
    ) : array[T]
    where K : IComparable[K]
    requires arr.Length > 0
    {
      def res = List();
      res.Add(arr[0]);
      mutable key = selector(arr[0]);
      
      foreach(i in [1 .. arr.Length - 1])
      {
        def elem = arr[i];
        def cmp = selector(elem).CompareTo(key);
        when(cmp > 0) res.Clear();
        unless(cmp < 0)
        {
          res.Add(elem); 
          key = selector(elem);
        }
      };
      
      res.ToArray();
    }
    
    
    public Minimum[T](
      [NotNull] this arr : array[T],
    ) : T
    where T : IComparable[T]
    requires arr.Length > 0
    {
      mutable res = arr[0];
      foreach(elem in arr)
        when(elem.CompareTo(res) < 0) res = elem;
      res
    }
    
    
    public MinimumBy[T, K](
      [NotNull] this arr : array[T],
      [NotNull] selector : T -> K
    ) : T
    where K : IComparable[K]
    requires arr.Length > 0
    {
      mutable res = arr[0];
      mutable key = selector(res);
      foreach(elem in arr)
        when(selector(elem).CompareTo(key) < 0)
        {
          res = elem;
          key = selector(res);
        };
      res
    }
    
    
    public MinimumsBy[T, K](
      [NotNull] this arr : array[T],
      [NotNull] selector : T -> K
    ) : array[T]
    where K : IComparable[K]
    requires arr.Length > 0
    {
      def res = List();
      res.Add(arr[0]);
      mutable key = selector(arr[0]);
      
      foreach(i in [1 .. arr.Length - 1])
      {
        def elem = arr[i];
        def cmp = selector(elem).CompareTo(key);
        when(cmp < 0) res.Clear();
        unless(cmp > 0)
        {
          res.Add(elem); 
          key = selector(elem);
        }
      };
      
      res.ToArray();
    }
    
    //=================
    // Building lists
    //=================
    //--------
    // Scans
    //--------
    
    /// <summary>
    /// Reduces the array from left to right using the specified binary function
    /// starting with the specified accumulator value, and return the array of 
    /// intermediate accumulator values.
    /// </summary>
    /// <typeparam name="T">The type of the elements in the array.</typeparam>
    /// <typeparam name="TAccumulator">The type of the accumulator.</typeparam>
    /// <param name="arr">The sequence to fold.</param>
    /// <param name="f">The binary function.</param>
    /// <param name="acc">The initial value of the accumulator.</param>
    /// <returns>The array of accumulator values.</returns>
    public Scan[TAccumulator, T](
      [NotNull] this arr : array[T],
      mutable   acc      : TAccumulator,
      [NotNull] f        : TAccumulator * T -> TAccumulator
    ) : array[TAccumulator]
    {
      def result = array(arr.Length + 1);
      result[0] = acc;
      foreach (value in arr with i)
      {
        acc = f(acc, value);
        result[i + 1] = acc;
      }
      result
    }
    
    /// <summary>
    /// Reduces the array from right to left using the specified binary function
    /// starting with the specified accumulator value, and return the array of 
    /// intermediate accumulator values.
    /// </summary>
    /// <typeparam name="T">The type of the elements in the array.</typeparam>
    /// <typeparam name="TAccumulator">The type of the accumulator.</typeparam>
    /// <param name="arr">The array to fold.</param>
    /// <param name="f">The binary function.</param>
    /// <param name="acc">The initial value of the accumulator.</param>
    /// <returns>The array of accumulator values.</returns>
    public ScanRight[TAccumulator, T](
      [NotNull] this arr : array[T],
      mutable   acc      : TAccumulator,
      [NotNull] f        : T * TAccumulator -> TAccumulator
    ) : array[TAccumulator]
    {
      def result = array(arr.Length + 1);
      result[arr.Length] = acc;
      foreach (i in [arr.Length-1, arr.Length-2 .. 0])
      {
        acc = f(arr[i], acc);
        result[i] = acc;
      }
      result
    }
    
    //--------------------
    // Accumulating maps
    //--------------------
    
    
    public MapAcc[TAcc, T, R](
      [NotNull] this arr : array[T],
      mutable        acc : TAcc,
      [NotNull]      f   : (TAcc * T) -> (TAcc * R)
    ) : TAcc * array[R]
    {
      def result = array(arr.Length);
      foreach(item in arr with i)
        (acc, result[i]) = f(acc, item);
      (acc, result)
    }
    
    
    public MapAccRight[TAcc, T, R](
      [NotNull] this arr : array[T],
      mutable        acc : TAcc,
      [NotNull]      f   : (TAcc * T) -> (TAcc * R)
    ) : TAcc * array[R]
    {
      def result = array(arr.Length);
      foreach (i in [arr.Length-1, arr.Length-2 .. 0])
        (acc, result[i]) = f(acc, arr[i]);
      (acc, result)
    }
    
    //------------
    // Unfolding
    //------------
    
    
    public Replicate[T](item : T, times : int) : array[T]
    {
      if(times > 0)
      {
        def result = array(times);
        foreach(i in [0 .. times - 1]) result[i] = item;
        result
      }
      else
        array(0)
    }
    
    
    public ReplicateResult[T](f : void -> T, times : int) : array[T]
    {
      if(times > 0)
      {
        def result = array(times);
        foreach(i in [0 .. times - 1]) result[i] = f();
        result
      }
      else
        array(0)
    }
    
    /// <summary>
    /// Produces an array from the given seed using the specified function.
    /// Function should return <c>None</c> in order to finish constructing the array;
    /// if <paramref name="f"/> returns a pair <c>x, state</c>, then <c>x</c> is added to the list
    /// and <paramref name="func"/> will next be called with <c>state</c> as its argument.
    /// </summary>
    /// <typeparam name="T">The type of the elements of the sequence.</typeparam>
    /// <typeparam name="TState">The type of the state.</typeparam>
    /// <param name="f">The function.</param>
    /// <param name="init">The initial state.</param>
    /// <returns></returns>
    public Unfold[TState, T](
      mutable   init : TState,
      [NotNull] f    : TState -> option[TState * T]
    ) : array[T]
    {
      def result = List();
      def loop(state)
      {
        | Some((s, r)) => {
          result.Add(r);
          loop(f(s))
        }
        | None => result
      }
      loop(f(init)).ToArray();
    }
    
    
    public UnfoldRight[TState, T](
      mutable   init : TState,
      [NotNull] f    : TState -> option[TState * T]
    ) : array[T]
    {
      def result = Stack();
      def loop(state)
      {
        | Some((s, r)) => {
          result.Push(r);
          loop(f(s))
        }
        | None => result
      }
      loop(f(init)).ToArray();
    }
    
    //===========
    // Subarrays
    //===========
    //----------------------
    // Extracting subarrays
    //----------------------
    
    public Get[T](
      [NotNull] this arr : array[T],
      n : int
    ) : array[T]
    {
      if (n > 0)
      {      
        def len = if(arr.Length >= n) n else arr.Length;
        def res = array(len);
        Array.Copy(arr, 0, res, 0, len);
        res
      }
      else
      {
        array(0) 
      }
    }
    
    
    public GetExactly[T](
      [NotNull] this arr : array[T],
      n : int
    ) : array[T]
    requires arr.Length >= n && n >= 0
    {
      def res = array(n);
      Array.Copy(arr, 0, res, 0, n);
      res
    }
    
    #warning not tested
    public GetRight[T](
      [NotNull] this arr : array[T],
      n : int
    ) : array[T]
    {
      arr.Drop(arr.Length - n)
    }
    
    public GetRightExactly[T](
      [NotNull] this arr : array[T],
      n : int
    ) : array[T]
    requires arr.Length >= n && n >= 0
    {
      arr.DropExactly(arr.Length - n)
    }
    
    
    public DropExactly[T](
      [NotNull] this arr : array[T],
      n : int
    ) : array[T]
    requires arr.Length >= n && n >= 0
    {
      def res = array(arr.Length - n);
      Array.Copy(arr, n, res, 0, res.Length);
      res
    }
    
    
    public Drop[T](
      [NotNull] this arr : array[T],
      n : int
    ) : array[T]
    {
      if (n > 0)
      {
        def len = if(arr.Length >= n) n else arr.Length;
        arr.DropExactly(len)
      }
      else
      {
        arr.Copy()
      }
    }
    
    
    public DropRightExactly[T](
      [NotNull] this arr : array[T],
      n : int
    ) : array[T]
    requires arr.Length >= n && n >= 0
    {
      def res = array(arr.Length - n);
      Array.Copy(arr, 0, res, 0, res.Length);
      res
    }
    
    
    public DropRight[T](
      [NotNull] this arr : array[T],
      n : int
    ) : array[T]
    {
      if (n > 0)
      {
        def len = if(arr.Length >= n) n else arr.Length;
        def res = array(arr.Length - len);
        Array.Copy(arr, 0, res, 0, res.Length);
        res
      }
      else
      {
        arr.Copy() 
      }
    }
    
    
    public DropWhile[T](
      [NotNull] this arr : array[T],
      [NotNull]     pred : T -> bool
    ) : array[T]
    {
      def i = arr.CountWhile(pred);
      arr.DropExactly(i);
    }
    
    
    public DropRightWhile[T](
      [NotNull] this arr : array[T],
      [NotNull]     pred : T -> bool
    ) : array[T]
    {
      def i = arr.CountRightWhile(pred);
      arr.DropRightExactly(i);
    }
    
    
    public GetWhile[T](
      [NotNull] this arr : array[T],
      [NotNull]     pred : T -> bool
    ) : array[T]
    {
      def i = arr.CountWhile(pred);
      arr.GetExactly(i);
    }
    
    #warning not tested
    
    public GetWhileAcc[T, Acc](
      [NotNull] this arr : array[T],
      mutable        acc : Acc,
      [NotNull]     pred : Acc * T -> Acc * bool
    ) : Acc * array[T]
    {
      def (acc',i) = arr.CountWhileAcc(acc, pred);
      (acc', arr.GetExactly(i))
    }
    
    
    public GetRightWhile[T](
      [NotNull] this arr : array[T],
      [NotNull]     pred : T -> bool
    ) : array[T]
    {
      def i = arr.CountRightWhile(pred);
      arr.GetRightExactly(i);
    }
    
    
    public CountWhile[T](
      [NotNull] this arr : array[T],
      [NotNull]     pred : T -> bool
    ) : int
    {
      exit : { 
        foreach(x in arr with i)
          unless(pred(x)) exit(i);
        arr.Length
      }
    }
    
    
    public CountWhileAcc[T, Acc](
      [NotNull] this arr : array[T],
      mutable        acc : Acc,
      [NotNull]     pred : Acc * T -> Acc * bool
    ) : Acc * int
    {
      exit : { 
        foreach(x in arr with i)
        {
          def(acc', b) = pred(acc, x);
          acc = acc';
          unless(b) exit((acc, i));
        }
        (acc, arr.Length)
      }
    }
    
    
    public CountRightWhile[T](
      [NotNull] this arr : array[T],
      [NotNull]     pred : T -> bool
    ) : int
    {
      exit : { 
        foreach(i in [arr.Length-1, arr.Length-2 .. 0])
          unless(pred(arr[i])) exit(arr.Length - i - 1);
        arr.Length
      }
    }
    
    
    public CountUntil[T](
      [NotNull] this arr : array[T],
      [NotNull]     pred : T -> bool
    ) : int
    {
      exit : { 
        foreach(x in arr with i)
          when(pred(x)) exit(i);
        arr.Length
      }
    }
    
    #warning not tested
    
    public CountRightUntil[T](
      [NotNull] this arr : array[T],
      [NotNull]     pred : T -> bool
    ) : int
    {
      exit : { 
        foreach(i in [arr.Length-1, arr.Length-2 .. 0])
          when(pred(arr[i])) exit(arr.Length - i - 1);
        arr.Length
      }
    }
    
    
    public SplitExactlyAt[T](
      [NotNull] this arr : array[T],
                     i   : int
    ) : array[T] * array[T]
    {
      (arr.GetExactly(i), arr.DropExactly(i))
    }
    
    
    public SplitAt[T](
      [NotNull] this arr : array[T],
                     i   : int
    ) : array[T] * array[T]
    {
      match(i)
      {
        | i when i <= 0          => (array(0), arr.Copy())
        | i when i >= arr.Length => (arr.Copy(), array(0))
        |                      _ => (arr.GetExactly(i), arr.DropExactly(i))
      }
    }
    
    
    public Span[T](
      [NotNull] this arr : array[T],
      [NotNull]     pred : T -> bool
    ) : array[T] * array[T]
    {
      def start = arr.CountWhile(pred);
      arr.SplitExactlyAt(start);
    }
    
    
    public Break[T](
      [NotNull] this arr : array[T],
      [NotNull]     pred : T -> bool
    ) : array[T] * array[T]
    {
      def start = arr.CountUntil(pred);
      arr.SplitExactlyAt(start);
    }
    
    
    public Organize[T](
      [NotNull] this arr : array[T]
    ) : array[array[T]]
    {
      if(arr.Length > 0)
      {
        def cmp = EqualityComparer.Default;
        mutable buffer = List();
        buffer.Add(arr[0]);
        mutable curr = arr[0];
        def result = List();
        foreach(i in [1..arr.Length-1])
        {
          def x = arr[i];
          unless(cmp.Equals(curr,x))
          {
            result.Add(buffer.ToArray());
            buffer = List();
            curr = x;
          }
          buffer.Add(x)
        }
        result.Add(buffer.ToArray());
        result.ToArray()
      }
      else
        array(0)
    }
    
    
    public OrganizeBy[T, K](
      [NotNull] this arr : array[T],
      [NotNull] selector : T -> K
    ) : array[K * array[T]]
    {
      if(arr.Length > 0)
      {
        def cmp = EqualityComparer.Default;
        mutable buffer = List();
        buffer.Add(arr[0]);
        mutable curr = selector(arr[0]);
        def result = List();
        foreach(i in [1..arr.Length-1])
        {
          def x = arr[i];
          def key = selector(x);
          unless(cmp.Equals(curr,key))
          {
            result.Add((curr, buffer.ToArray()));
            buffer = List();
            curr = key;
          }
          buffer.Add(x)
        }
        result.Add((curr, buffer.ToArray()));
        result.ToArray()
      }
      else
        array(0)
    }
    
    
    public Categorize[T](
      [NotNull] this arr : array[T]
    ) : array[array[T]]
    {
      def dict = Dictionary();
      def keysByOrder = List();
      foreach(x in arr)
      {
        if(dict.ContainsKey(x))
        {
          dict[x].Add(x)
        }
        else
        {
          keysByOrder.Add(x);
          def category = List();
          category.Add(x);
          dict.Add(x, category);
        }
      }
      def result = array(keysByOrder.Count);
      foreach(key in keysByOrder with i)
        result[i] = dict[key].ToArray();
      result
    }
    
    
    public CategorizeBy[T, K](
      [NotNull] this arr : array[T],
      [NotNull] selector : T -> K
    ) : array[K * array[T]]
    {
      def dict = Dictionary();
      def keysByOrder = List();
      foreach(x in arr)
      {
        def key = selector(x);
        if(dict.ContainsKey(key))
        {
          dict[key].Add(x)
        }
        else
        {
          keysByOrder.Add(key);
          def category = List();
          category.Add(x);
          dict.Add(key, category);
        }
      }
      def result = array(keysByOrder.Count);
      foreach(key in keysByOrder with i)
        result[i] = (key, dict[key].ToArray());
      result
    }
    
    
    public Inits[T](
      [NotNull] this arr : array[T]
    ) : array[array[T]]
    {
      def result = array(arr.Length + 1);
      foreach(i in [0 .. result.Length - 1])
        result[i] = arr.GetExactly(i);
      result
    }
    
    
    public Tails[T](
      [NotNull] this arr : array[T]
    ) : array[array[T]]
    {
      def result = array(arr.Length + 1);
      foreach(i in [0 .. result.Length - 1])
        result[i] = arr.DropExactly(i);
      result
    }
    
    //-------------
    // Predicates
    //-------------
    
    #warning not tested
    
    public SequenceEq[T](
      [NotNull] this arr1 : array[T],
      [NotNull]      arr2 : array[T],
    ) : bool
    {
      def cmp = EqualityComparer.Default;
      if(arr1.Length == arr2.Length)
      exit : {
        foreach(i in [0..arr1.Length - 1])
          unless(cmp.Equals(arr1[i],arr2[i])) 
            exit(false);
        true
      }
      else
        false
    }
        
    public SequenceEq'[T](
      [NotNull] this arr1 : array[T],
      [NotNull]      arr2 : array[T],
    ) : bool
    where T : IEquatable[T]
    {
      if(arr1.Length == arr2.Length)
      exit : {
        foreach(i in [0..arr1.Length - 1])
          unless(arr1[i].Equals(arr2[i])) exit(false);
        true
      }
      else
        false
    }
    
    public SequenceEq''[T](
      [NotNull] this arr1 : array[T],
      [NotNull]      arr2 : array[T],
    ) : bool
    where T : IEquatable[T]
    {
      def cmp = EqualityComparer.Default;
      if(arr1.Length == arr2.Length)
      exit : {
        foreach(i in [0..arr1.Length - 1])
          unless(cmp.Equals(arr1[i],arr2[i])) exit(false);
        true
      }
      else
        false
    }
    
    #warning not tested
    
    public SetEq[T](
      [NotNull] this arr1 : array[T],
      [NotNull]      arr2 : array[T],
    ) : bool
    {
      def set = HashSet(arr1);
      set.SetEquals(arr2)
    }
    
    
    public IsPrefixOf[T](
      [NotNull] this prefix : array[T],
      [NotNull]         arr : array[T]
    ) : bool
    {
      IsPrefixOfFrom(prefix, arr, 0)
    }
    
    private IsPrefixOfFrom[T](
      [NotNull] prefix : array[T],
      [NotNull]    arr : array[T],
                 start : int
    ) : bool
    {
      def cmp = EqualityComparer.Default;
      if(prefix.Length <= arr.Length - start)
      {
        exit : {
          foreach(x in prefix with i)
            unless(cmp.Equals(x,arr[i + start])) 
              exit(false);
          true
        }
      }
      else
        false
    }
    
    
    public IsInfixOf[T](
      [NotNull] this infix : array[T],
      [NotNull]        arr : array[T]
    ) : bool
    {
      if(infix.Length > 0)
      exit : {
       foreach(i in [0 .. arr.Length - infix.Length])
         when(IsPrefixOfFrom(infix, arr, i)) exit(true);
       false
      }
      else
        true
    }
    
    
    public IsSuffixOf[T](
      [NotNull] this suffix : array[T],
      [NotNull]         arr : array[T]
    ) : bool
    {
      def cmp = EqualityComparer.Default;
      if(suffix.Length <= arr.Length)
      {
        def delta = arr.Length - suffix.Length;
        exit : {
          foreach(x in suffix with i)
            unless(cmp.Equals(x,arr[i + delta])) 
              exit(false);
          true
        }
      }
      else
        false
    }
    
    //==================
    // Searching lists
    //==================
    //------------------------
    // Searching by equality
    //------------------------
    
    
    public ContainsElem[T](
      [NotNull] this arr : array[T],
      elem : T
    ) : bool
    {
      def cmp = EqualityComparer.Default;
      exit : {
       foreach(x in arr)
         when(cmp.Equals(x,elem)) 
           exit(true);
       false
      }
    }
    
    #warning not tested
    public ContainsElemBy[T, K](
      [NotNull] this arr : array[T],
                     key : K,
                selector : T -> K
    ) : bool
    {
      def cmp = EqualityComparer.Default;
      exit : {
       foreach(x in arr)
         when(cmp.Equals(selector(x),key)) 
           exit(true);
       false
      }
    }
    
    public ElementOf[T](
      this elem : T,
      [NotNull] arr : array[T]
    ) : bool
    {
      arr.ContainsElem(elem) 
    }
    
    //----------------------------
    // Searching with a predicate
    //----------------------------
    
    
    public Find[T](
      [NotNull] this arr : array[T],
      [NotNull]     pred : T -> bool
    ) : option[T]
    where T : IEquatable[T]
    {
      exit : {
       foreach(x in arr)
         when(pred(x)) exit(Some(x));
       None()
      }
    }
    
    /// <summary>
    /// Filters an array of values based on a predicate.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="arr">The array.</param>
    /// <param name="pred">The predicate.</param>
    /// <returns></returns>
    public Filter[T](
      [NotNull] this arr : array[T],
      [NotNull]     pred : T -> bool
    ) : array[T]
    {
      def result = List(arr.Length);
      foreach(x when pred(x) in arr)
         result.Add(x);
      result.ToArray()
    }
    
    /// <summary>
    /// Filters an array of values based on a predicate.
    /// The integer passed to the predicate indicates the index of element.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="arr">The array.</param>
    /// <param name="pred">The predicate.</param>
    /// <returns></returns>
    public FilterI[T](
      [NotNull] this arr : array[T],
      [NotNull]     pred : int * T -> bool //TO DO подумать над тем, стоит ли использовать порядок парметров IterI или LINQ 
    ) : array[T]
    {
      def result = List(arr.Length);
      foreach(x when pred(i, x) in arr with i)
         result.Add(x);
      result.ToArray()
    }
    
    
    #warning not tested
    public FilterAcc[T, Acc](
      [NotNull] this arr : array[T],
      mutable        acc : Acc,
      [NotNull]     pred : Acc * T -> Acc * bool
    ) : Acc * array[T]
    {
      def result = List(arr.Length);
      foreach(x in arr)
      {
        def (acc', b) = pred(acc, x);
        when (b) result.Add(x);
        acc = acc';
      }
      (acc, result.ToArray())
    }
    
    
    public Partition[T](
      [NotNull] this arr : array[T],
      [NotNull]     pred : T -> bool
    ) : array[T] * array[T]
    {
      def res1 = List(arr.Length);
      def res2 = List(arr.Length);
      foreach(x in arr)
        if (pred(x))
         res1.Add(x);
        else
         res2.Add(x);
      (res1.ToArray(), res2.ToArray())
    }
    
    //-----------
    // Indexing
    //-----------
    
    
    public Nth[T](
      [NotNull] this arr : array[T],
                       i : int
    ) : option[T]
    {
      if(i >= 0 && i < arr.Length)
        Some(arr[i])
      else
        None()
    }
    
    
    public IndexOf[T](
      [NotNull] this arr : array[T],
                    elem : T
    ) : option[int]
    {
      def i = Array.IndexOf(arr, elem);
      if(i > -1) Some(i) else None()
    }
    
    
    public IndicesOf[T](
      [NotNull] this arr : array[T],
                    elem : T
    ) : array[int]
    {
      def cmp = EqualityComparer.Default;
      def result = List();
      foreach(x when cmp.Equals(x,elem) in arr with i)
         result.Add(i);
      result.ToArray()
    }
    
    /// <summary>
    /// Searches for an element that matches the conditions defined by the specified predicate,
    /// and returns the zero-based index of the first occurrence within the entire array,
    /// or None if there is no such element.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="arr">The array.</param>
    /// <param name="pred">The predicate.</param>
    /// <returns></returns>
    public FindIndex[T](
      [NotNull] this arr : array[T],
      [NotNull]     pred : T -> bool
    ) : option[int]
    {
      exit : {
       foreach(x in arr with i)
         when(pred(x)) exit(Some(i));
       None()
      }
    }
    
    /// <summary>
    /// Searches for all elements that matches the conditions defined by the specified predicate,
    /// and returns array of the zero-based indices.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="arr">The array.</param>
    /// <param name="pred">The predicate.</param>
    /// <returns></returns>
    public FindIndices[T](
      [NotNull] this arr : array[T],
      [NotNull]     pred : T -> bool
    ) : array[int]
    {
      def result = List();
      foreach(x when pred(x) in arr with i)
         result.Add(i);
      result.ToArray()
    }
    
    
    public InsertAt[T](
      [NotNull] this arr : array[T],
                    item : T,
                       i : int
    ) : array[T]
    {
      if(i >= 0 && i < arr.Length + 1)
        arr.InsertExactlyAt(item, i)
      else
        arr.Copy()
    }
    
    
    public InsertExactlyAt[T](
      [NotNull] this arr : array[T],
                    item : T,
                       i : int
    ) : array[T]
    requires i >= 0 && i < arr.Length + 1
    {
        def res = array(arr.Length + 1);
        Array.Copy(arr, 0, res, 0, i);
        Array.Copy(arr, i, res, i + 1, arr.Length - i);
        res[i] = item;
        res
    }
    
    //-------------------------------
    // Zipping and unzipping arrays
    //-------------------------------
    
    /// <summary>
    /// Takes two arrays and a function, calls the function on corresponding pairs
    /// and returns an array of the results.
    /// If one array is short, excess elements of the longer array are discarded.
    /// </summary>
    /// <param name="f">The function used to combine pairs.</param>
    /// <param name="arr1">The first array.</param>
    /// <param name="arr2">The second array.</param>
    /// <returns></returns>
    public ZipWith[From1, From2, To](
      [NotNull] this arr1 : array[From1],
      [NotNull]      arr2 : array[From2],
      [NotNull]         f : From1 * From2 -> To
    ) : array[To]
    {
      def len = Math.Min(arr1.Length, arr2.Length);
      def result = array(len);
      foreach(i in [0..len - 1])
        result[i] = f(arr1[i], arr2[i]);
      result
    }

    /// <summary>
    /// Takes three arrays and a function, calls the function on corresponding triples
    /// and returns an array of the results.
    /// If one array is short, excess elements of the longer array are discarded.
    /// </summary>
    /// <param name="f">The function used to combine triples.</param>
    /// <param name="arr1">The first array.</param>
    /// <param name="arr2">The second array.</param>
    /// <param name="arr3">The third array.</param>
    /// <returns></returns>
    #warning not tested
    public Zip3With[From1, From2, From3, To](
      [NotNull] this arr1 : array[From1],
      [NotNull]      arr2 : array[From2],
      [NotNull]      arr3 : array[From3],
      [NotNull]         f : From1 * From2 * From3 -> To
    ) : array[To]
    {
      def len = Math.Min(arr1.Length, Math.Min(arr2.Length, arr3.Length));
      def result = array(len);
      foreach(i in [0..len - 1])
        result[i] = f(arr1[i], arr2[i], arr3[i]);
      result
    }

    
    /// <summary>
    /// Takes two arrays and returns an array of corresponding pairs. 
    /// If one array is short, excess elements of the longer array are discarded.
    /// </summary>
    /// <param name="arr1">The first array.</param>
    /// <param name="arr2">The second array.</param>
    /// <returns></returns>
    public Zip[T1, T2](
      [NotNull] this arr1 : array[T1],
      [NotNull]      arr2 : array[T2],
    ) : array[T1*T2]
    {
      def len = Math.Min(arr1.Length, arr2.Length);
      def result = array(len);
      foreach(i in [0..len - 1])
        result[i] = (arr1[i], arr2[i]);
      result
    }
    
    /// <summary>
    /// Takes three arrays and returns an array of corresponding triples. 
    /// If one array is short, excess elements of the longer array are discarded.
    /// </summary>
    /// <param name="arr1">The first array.</param>
    /// <param name="arr2">The second array.</param>
    /// <param name="arr3">The third array.</param>
    /// <returns></returns>
    #warning not tested
    public Zip3[T1, T2, T3](
      [NotNull] this arr1 : array[T1],
      [NotNull]      arr2 : array[T2],
      [NotNull]      arr3 : array[T3]
    ) : array[T1*T2*T3]
    {
      def len = Math.Min(arr1.Length, Math.Min(arr2.Length, arr3.Length));
      def result = array(len);
      foreach(i in [0..len - 1])
        result[i] = (arr1[i], arr2[i], arr3[i]);
      result
    }
    
    /// <summary>
    /// Takes two arrays and a function, calls the function on corresponding pairs
    /// and returns an array of the results.
    /// </summary>
    /// <param name="f">The function used to combine pairs.</param>
    /// <param name="arr1">The first array.</param>
    /// <param name="arr2">The second array.</param>
    /// <returns></returns>
    public Map2[From1, From2, To](
      [NotNull] this arr1 : array[From1],
      [NotNull]      arr2 : array[From2],
      [NotNull]         f : From1 * From2 -> To
    ) : array[To]
    requires arr1.Length == arr2.Length
    {
      ZipWith(arr1, arr2, f)
    }
    
    #warning not tested
    public Map3[From1, From2, From3, To](
      [NotNull] this arr1 : array[From1],
      [NotNull]      arr2 : array[From2],
      [NotNull]      arr3 : array[From3],
      [NotNull]         f : From1 * From2 * From3 -> To
    ) : array[To]
    requires arr1.Length == arr2.Length && arr2.Length == arr3.Length
    {
      arr1.Zip3With(arr2, arr3, f)
    }
    
    /// <summary>
    /// Splits an array of pairs into a pair of arrays.
    /// </summary>
    /// <param name="arr">
    /// The array.
    /// </param>
    /// <returns></returns>
    public UnZip[T1, T2](
      [NotNull] this arr : array[T1*T2]
    ) : array[T1] * array[T2]
    {
      (arr.Firsts(), arr.Seconds()) 
    }
    
    
    public Firsts[T1, T2](
      [NotNull] this arr : array[T1*T2]
    ) : array[T1]
    {
      def result = array(arr.Length);
      foreach((x, _) in arr with i)
        result[i] = x;
      result
    }
    
    
    public Seconds[T1, T2](
      [NotNull] this arr : array[T1*T2]
    ) : array[T2]
    {
      def result = array(arr.Length);
      foreach((_, x) in arr with i)
        result[i] = x;
      result
    }
    
    //------------------
    // "Set" operations
    //------------------
    
    /// <summary>
    /// Returns new array without duplicate elements from a source array 
    /// by using the default equality comparer to compare values. 
    /// In particular, it keeps only the first occurrence of each element.    
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="arr">The array.</param>
    /// <returns></returns>
    public UniqueElements[T](
      [NotNull] this arr : array[T]
    ) : array[T]
    {
      Essence(arr)
    }

    /// <summary>
    /// Returns new array without duplicate elements from a source array 
    /// by using the default equality comparer to compare values. 
    /// In particular, it keeps only the first occurrence of each element.    
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="arr">The array.</param>
    /// <returns></returns>
    public Essence[T](
      [NotNull] this arr : array[T]
    ) : array[T]
    {
      def set = HashSet(arr);
      set.ToArray()
    }

    
    public EssenceBy[T, K](
      [NotNull] this arr : array[T],
      [NotNull] selector : T -> K 
    ) : array[T]
    {
      def set = HashSet(arr, SelectEqComparer(selector));
      set.ToArray()
    }
    
    
    public DeleteFirst[T](
      [NotNull] this arr : array[T],
      elem : T
    ) : array[T]
    {
      def cmp = EqualityComparer.Default;
      exit : {
      foreach(x in arr with i)
        when(cmp.Equals(elem,x))
        {
          def result = array(arr.Length - 1);
          Array.Copy(arr, 0, result, 0, i);
          Array.Copy(arr, i + 1, result, i, result.Length - i);
          exit(result);
        }
      arr.Copy()
      }
    }
       
    public DeleteFirstWhen[T](
      [NotNull] this arr : array[T],
      [NotNull]     pred : T -> bool
    ) : array[T]
    {
      exit : {
      foreach(x in arr with i)
        when(pred(x))
        {
          def result = array(arr.Length - 1);
          Array.Copy(arr, 0, result, 0, i);
          Array.Copy(arr, i + 1, result, i, result.Length - i);
          exit(result);
        }
      arr.Copy()
      }
    }
    
    public DeleteFirstBy[T, K](
      [NotNull] this arr : array[T],
                     key : K,
      [NotNull] selector : T -> K
    ) : array[T]
    {
      def cmp = EqualityComparer.Default;
      exit : {
      foreach(x in arr with i)
        when(cmp.Equals(key,selector(x)))
        {
          def result = array(arr.Length - 1);
          Array.Copy(arr, 0, result, 0, i);
          Array.Copy(arr, i + 1, result, i, result.Length - i);
          exit(result);
        }
      arr.Copy()
      }
    }
        
    public DeleteAll[T](
      [NotNull] this arr : array[T],
                    elem : T
    ) : array[T]
    {
      def cmp = EqualityComparer.Default;
      def result = List(arr.Length);
      foreach(x when !cmp.Equals(elem,x) in arr)
        result.Add(x);
      result.ToArray();
    }
    
    
    public DeleteWhen[T](
      [NotNull] this arr : array[T],
      [NotNull]     pred : T -> bool
    ) : array[T]
    {
      def result = List(arr.Length);
      foreach(x when !pred(x) in arr)
        result.Add(x);
      result.ToArray();
    }
    
    
    public DeleteAllBy[T, K](
      [NotNull] this arr : array[T],
                     key : K,
      [NotNull] selector : T -> K
    ) : array[T]
    {
      def cmp = EqualityComparer.Default;
      def result = List(arr.Length);
      foreach(x when !cmp.Equals(key,selector(x)) in arr)
        result.Add(x);
      result.ToArray();
    }
    
    
    public DeleteFirsts[T](
      [NotNull] this arr1 : array[T],
      [NotNull]      arr2 : array[T]
    ) : array[T]
    {
       arr1.Diff(arr2)
    }
    
    /// <summary>
    /// Produces the array difference of two arrays by using the default equality comparer to compare values.
    /// </summary>
    /// <param name="arr1">The first array.</param>
    /// <param name="arr2">The second array.</param>
    /// <returns></returns>
    public Diff[T](
      [NotNull] this arr1 : array[T],
      [NotNull]      arr2 : array[T]
    ) : array[T]
    {
       def set = HashSet(arr2);
       def result = List(arr1.Length);
       foreach(x when !set.Contains(x) in arr1)
         result.Add(x);
       result.ToArray();
    }
    
    
    public DiffBy[T, K](
      [NotNull] this arr1 : array[T],
      [NotNull]      arr2 : array[T],
      [NotNull] selector : T -> K 
    ) : array[T]
    {
      def set = HashSet(arr2, SelectEqComparer(selector));
      def result = List(arr1.Length);
      foreach(x when !set.Contains(x) in arr1)
       result.Add(x);
      result.ToArray();
    }
    
    
    public DeleteFirstsBy[T, K](
      [NotNull] this arr1 : array[T],
      [NotNull]      arr2 : array[T],
      [NotNull] selector : T -> K 
    ) : array[T]
    {
      arr1.DiffBy(arr2, selector)
    }
    
    
    public SetDiff[T](
      [NotNull] this arr1 : array[T],
      [NotNull]      arr2 : array[T] 
    ) : array[T]
    {
      def set = HashSet(arr1);
      set.ExceptWith(arr2);
      set.ToArray();
    }
    
    
    public SetDiffBy[T, K](
      [NotNull] this arr1 : array[T],
      [NotNull]      arr2 : array[T],
      [NotNull] selector : T -> K 
    ) : array[T]
    {
      def set = HashSet(arr1, SelectEqComparer(selector));
      set.ExceptWith(arr2);
      set.ToArray();
    }
    
    
    public SetAdd[T](
      [NotNull] this arr1 : array[T],
      [NotNull]      arr2 : array[T]
    ) : array[T]
    {
       def set = HashSet(arr1);
       set.UnionWith(arr2);
       set.ToArray()
    }
    
    
    public SetAddBy[T, K](
      [NotNull] this arr1 : array[T],
      [NotNull]      arr2 : array[T],
      [NotNull] selector : T -> K 
    ) : array[T]
    {
      def set = HashSet(arr1, SelectEqComparer(selector));
      set.UnionWith(arr2);
      set.ToArray()
    }    
    
    
    public Intersection[T](
      [NotNull] this arr1 : array[T],
      [NotNull]      arr2 : array[T]
    ) : array[T]
    {
       def set = HashSet(arr1);
       set.IntersectWith(arr2);
       set.ToArray()
    }
    
    
    public IntersectionBy[T, K](
      [NotNull] this arr1 : array[T],
      [NotNull]      arr2 : array[T],
      [NotNull] selector : T -> K 
    ) : array[T]
    {
      def set = HashSet(arr1, SelectEqComparer(selector));
      set.IntersectWith(arr2);
      set.ToArray()
    }    
    
    //---------------
    // Ordered lists
    //---------------
    
    
    public SortInplace[T](
      [NotNull] this arr : array[T]
    ) : array[T]
    where T : IComparable[T]
    {
      Array.Sort(arr);
      arr
    }
    
    
    public SortInplace[T](
      [NotNull] this arr : array[T],
      [NotNull]  compare : IComparer[T]
    ) : array[T]
    {
      Array.Sort(arr, compare);
      arr
    }
    
    
    public SortInplace[T](
      [NotNull] this arr : array[T],
      [NotNull]  compare : T * T -> int 
    ) : array[T]
    {
      Array.Sort(arr, Comparer(compare));
      arr
    }
    
    
    public SortInplaceBy[T, K](
      [NotNull] this arr : array[T],
      [NotNull] selector : T -> K 
    ) : array[T]
    where K : IComparable[K]
    {
      Array.Sort(arr, SelectComparer(selector));
      arr
    }
    
    
    public Sort[T](
      [NotNull] this arr : array[T]
    ) : array[T]
    where T : IComparable[T]
    {
      arr.Copy().SortInplace()
    }
    
    
    public Sort[T](
      [NotNull] this arr : array[T],
      [NotNull]  compare : IComparer[T] 
    ) : array[T]
    {
      arr.Copy().SortInplace(compare)
    }
    
    
    public Sort[T](
      [NotNull] this arr : array[T],
      [NotNull]  compare : T * T -> int 
    ) : array[T]
    {
      arr.Copy().SortInplace(compare)
    }
    
    
    public SortBy[T, K](
      [NotNull] this arr : array[T],
      [NotNull] selector : T -> K 
    ) : array[T]
    where K : IComparable[K]
    {
      arr.Copy().SortInplaceBy(selector)
    }
    
    
    private BinarySearch[T](
      [NotNull]  arr : array[T],
                  lo : int,
                  hi : int,
                item : T
    ) : int
    where T : IComparable[T]
    {
      if (lo <= hi)
      {
        def di = hi - lo;
        def i = lo + (di >> 1);
        def cmpResult = item.CompareTo(arr[i]);

        if (cmpResult == 0 || di == 0)
          i
        else if (cmpResult < 0)
          BinarySearch (arr, i + 1, hi, item)
        else
          BinarySearch (arr, lo, i - 1, item)
      }
      else
        ~lo
    }
    
    
    private BinarySearchBy[T](
      [NotNull]  arr : array[T],
                  lo : int,
                  hi : int,
                 cmp : T -> int
    ) : int
    {
      if (lo <= hi)
      {
        def di = hi - lo;
        def i = lo + (di >> 1);
        def cmpResult = cmp(arr[i]);

        if (cmpResult == 0 || di == 0)
          i
        else if (cmpResult < 0)
          BinarySearchBy (arr, i + 1, hi, cmp)
        else
          BinarySearchBy (arr, lo, i - 1, cmp)
      }
      else
        ~lo
    }
    
    //не дает гарантии, что вставка будет осуществлена в конец ряда элементов с одинаковыми значениями.
    
    
    #warning TO DO
    public Insert[T](
      [NotNull] this arr : array[T],
                    item : T
    ) : array[T]
    where T : IComparable[T]
    {
      def i = arr.CountWhile(x => x.CompareTo(item) <= 0); //BinarySearch(arr, 0, arr.Length - 1, item);
      arr.InsertAt(item, i /*+ 1*/)
    }
    
    #warning TO DO
    public InsertBy[T, K](
      [NotNull] this arr : array[T],
                    item : T,
                selector : T -> K
    ) : array[T]
    where K : IComparable[K]
    {
      def key = selector(item);
      def i = arr.CountWhile(x => selector(x).CompareTo(key) <= 0);//BinarySearchBy(arr, 0, arr.Length - 1, x => selector(x).CompareTo(key));
      arr.InsertAt(item, i /*+ 1*/)
    }
  }
  
  
  [Record]
  public class Comparer[T] : IComparer[T]
  {
    _comparer : T * T -> int;
    
    public Compare(a : T, b : T) : int
    {
      _comparer(a, b)
    }
  }
  
  
  [Record]
  public class SelectComparer[T, K] : IComparer[T]
    where K : IComparable[K]
  {
    _select : T -> K;
    
    public Compare(a : T, b : T) : int
    {
      _select(a).CompareTo(_select(b))
    }
  }
  
  
  [Record]
  public class EqComparer[T] : IEqualityComparer[T]
  {
    _eq : T * T -> bool;
    
    _hash : T -> int;
    
    public GetHashCode(a : T) : int
    {
      _hash(a)
    }
    
    public Equals(a : T, b : T) : bool
    {
      _eq(a, b)
    }
  }
  
  
  [Record]
  public class SelectEqComparer[T, K] : IEqualityComparer[T]
  {
    _select : T -> K;
    
    public GetHashCode(a : T) : int
    {
      _select(a).GetHashCode()
    }
    
    public Equals(a : T, b : T) : bool
    {
      _select(a).Equals(_select(b))
    }
  }
}
